Now that we have completed the $O(n)$ partitioning phase on the initial array $A$, resulting in the pivot (6) being correctly placed, we move into the recursive step of Quick Sort.

  • Quick Sort is inherently a divide-and-conquer algorithm; once the pivot is fixed, the problem is divided into two entirely independent sub-problems: sorting the elements smaller than the pivot (Left Sub-array) and sorting the elements larger than the pivot (Right Sub-array).
  • We first tackle the Left Sub-array, $A[low \dots p_{index}-1]$, which currently holds the values [2, 5, 1].
  • This recursive call repeats the entire process: a new pivot is chosen within this sub-array, it is partitioned, and then the resulting segments are subjected to further recursive calls until the base case (an array of size $\leq 1$) is reached.
Python Implementation: quickSort
1# The main recursive logic of Quick Sort
2def quickSort(A, low, high):
3    # Base Case: Stop recursion if the segment has 0 or 1 elements
4    if low < high: 
5        # 1. Divide: Execute O(n) partitioning on the segment
6        # (Assumes partition() function is defined and returns the final pivot index)
7        p_index = partition(A, low, high) 
8
9        # 2. Conquer (Left): Recurse on the elements to the left of the pivot
10        quickSort(A, low, p_index - 1)
11
12        # 3. Conquer (Right): Recurse on the elements to the right of the pivot
13        quickSort(A, p_index + 1, high)
14
15# Initial call on the Example_Array [8, 2, 5, 1, 6]
16# After Slide 27, p_index=3, A=[2, 5, 1, 6, 8]
17# The next steps focus on line 10: quickSort(A, 0, 2)